Combinatorial layout design has been a challenging research topic in engineering as well as operation research. In general, combinatorial layout design is a process of allocating a set of space elements on a layout base, performing grouping and designing topological and geometrical relationships between them according to certain design objectives and constraints. Therefore, a wide variety of application areas ranging from family mould layout design, architectural floor plan layout design and component space layout design to circuit board layout design, page layout design and user-interface menu layout design involve combinatorial layout design.
For example, family mould layout design is one of good application examples of combinatorial layout design, Family moulds are widely used in some industries, such as toys and domestic products, because family moulds can offer an efficient and economical way to produce dissimilar plastic parts of the same plastic material and colour for small-to-medium production volume. In Family Mould Layout Design (FMLD), Family Mould Cavity and Runner Layout Design (FMCRLD) is the most critical task that significantly affects the cost and performance of a family mould because it determines many key design and cost factors such as filling balance performance, runner cost, mould insert cost, mould base cost and so forth. Each family mould is custom-made and unique. Different family moulds must be newly designed to meet different design requirements and constraints. Therefore, FMCRLD is non-repetitive and generative. Besides, FMCRLD involves a large number of combinations of various cavity layout and associated runner layout design alternatives and design considerations. In practice, it is virtually impossible for mould designers to try out all possible design alternatives manually to find the best trade-off solution between mould performance and cost. Existing human-dependent manual FMCRLD methods and the shortage of experienced mould designers cause long design lead time, non-optimum designs and costly human errors. FMCRLD is demanding and experience-dependent. Performing FMCRLD can be regarded as a “black art” of family mould design. A computer-based design tool to assist less experienced mould designers in performing FMCRLD is urgently needed. However, over the years, no published research, commercial software package or patented system can support FMCRLD automation and optimisation. For example, most Mechanical Computer-Aided Design (MCAD) systems can provide parametric cavity layout functions that can automate routine and regular cavity layout design of “One Product Moulds” using pre-defined standard cavity layout configuration templates. However, they cannot support FMCRLD automation and optimisation. Research on mould design has been widely reported over the years. However, research on FMCRLD automation and optimisation has gained little attention. No previous research can automatically generate a global optimum FMCRLD for mass production of complex-shaped parts (with no geometric limitation) considering a number of mould layout design objectives (such as maximization of filling balance performance, clamping force balance performance and drop time performance, and minimization of mould base cost, mould insert cost, runner scrap cost, slider cost and injection moulding cost) and constraints (such as mould base size limitations of customer's available injection moulding machines).
In family mould design, runner system balancing is one of the most important issues. Traditionally, runner and gate design are experience-dependent. In the past, a balanced runner system was achieved by adding runner shut-offs, using flow restrictors or adjusting gate sizes in the test-shot phase based on a trial-and-error basis. This iterative process of testing and re-machining on the mould is very costly and time-consuming. Today, through the use of advanced commercial mould flow Computer-Aided Engineering (CAE) simulation software packages, mould designers can determine the diameters of each individual runner segments of a given initial runner layout design to achieve artificial filling balance of a family mould before building the mould. However, it still require an experienced engineer to provide an initial runner layout and gate design beforehand, and correctly diagnose the simulation results and adjust the diameter of each runner segment based on a trial-and-error basis. Moreover, artificial filling balance of family moulds should be done by balancing the pressure drops in each flow branch with a proper cavity layout, runner lengths and diameters. A better FMCRLD can improve the artificial filling balance performance with a wider process window. However, existing commercial mould flow CAE software packages cannot considerate numerous combinations of FMCRLD automatically when performing artificial filling balance of family moulds. Because of the costly, tedious and time-consuming data preparation for filling balance analysis of numerous different FMCRLD, it is virtually impossible for mould designers to try all possible FMCRLD combinations and do such time-consuming mould filling analysis to fine-tune all of them one by one to search for the best solution. Over the years, many researchers have attempted to address the problems of runner system balancing for multiple-cavity moulds (including family moulds) using various optimisation approaches. However, all the previous research on runner system balancing did not consider the numerous possible combinations of different runner layout design interrelated with different cavity layout design in family moulds.
In other application areas, similar to family mould layout design, architectural space layout design, component space layout design, circuit board layout design, page layout design, user-interface menu layout design and so forth also involve allocating a set of space elements on a layout base, performing grouping and designing topological and geometrical relationships between them satisfying their specific design objectives and constraints. All of them are complex, combinatorial, non-repetitive, generative and human-dependent. Some specialised software tools can support designers to produce a geometrical layout design. However, when human designers deal with large and complex layout design problems, they easily get bored, distracted and tend to make mistakes. A good layout design still highly depends on a human designer's experience, knowledge, and creative ability. Combinatorial layout design automation and optimisation is full of challenges. Traditional design automation approaches, such as rule based reasoning, case-based reasoning and parametric design template, cannot produce truly creative, unpredictable or novel layout design solutions because they are unable to imitate human creativity based on pre-processed human problem-solving knowledge or human-generated solutions. Moreover, a solution space of a combinatorial layout design problem is so large that design knowledge cannot be captured, formulated, reused and represented in the form of rules, cases or design templates efficiently. On the other hand, traditional optimisation techniques, such as linear programming, branch and bound and gradient-based algorithms have been adopted to find the optimum strip packing layout design and container stuffing. These traditional optimisation techniques are efficient to search for the nearest local optimal solution with respect to the given initial solution. However, they are limited to a narrow class of simple layout problems where explicit mathematical equations describing the objective functions and constraints are available. In practice, finding a global optimum layout solution to a combinatorial layout design problem cannot be treated as an ordinary design parameter optimisation problem with a fixed number of variables based on a given initial layout design. In addition, layout design objectives and constraints and interactions among them are difficult to build as true mathematical models. More importantly, a search space of a combinatorial layout design problem is so large that optimisation should aim at searching for a population of good layout design solutions rather than a single local optimum one. In addition to the aforementioned optimisation techniques, Heuristic Rule-based (HR) algorithms are commonly used to solve specific types of packing and cutting stock problems. Previous research demonstrated that acceptable layout solutions could be generated efficiently based on special heuristic rules derived from common sense or experiences. However, these HR approaches are only applicable to a specific class of component space layout design problems where well-formed heuristic rules are available. Moreover, because of these reasons, such traditional optimisation techniques are unable to navigate such large search spaces to find near optimum solutions globally and are likely to be inferior local optima. In order to overcome the limitations of such traditional optimisation techniques, other researchers focused on seeking optimum layout solutions globally using Meta-Heuristic Search (MHS) techniques, such as Tabu Search (TS), Simulated Annealing (SA) and Genetic Algorithms (GA). TS is a dynamic neighbourhood search technique combined with memory-based strategies. It has been successfully applied to many combinatorial component space layout optimisation problems such as the two-dimensional cutting stock problem and three-dimensional bin-packing problem. Meanwhile, SA is an iterative improvement algorithm simulating the metallurgical annealing of heated metals. It has been widely used in circuit layout design, manufacturing facility layout design, three-dimensional mechanical and electro-mechanical component layout design and Heat, Ventilation and Air Conditioning (HVAC) routing layout design. GA is a stochastic search technique inspired by the biological phenomenon of the natural evolutionary process of survival of the fittest. It has been proven to be reliable and able to deal with complex combinatorial and multi-objective layout problems in a wide variety of application areas ranging from runner size optimisation and strip packing layout design to floor plan layout design and Very-Large-Scale-Integration (VLSI) circuit layout design. GA is superior to TS and SA because GA can deal with populations of solutions rather than a single solution. Therefore, GA can explore the neighbourhood of the whole population and does not strongly rely on the initial solution. Besides, GA can exchange the information of a large set of parallel solutions in the population through the evolutionary process. Thus GA appears to show great potential to support combinatorial layout design optimisation with its explorative and generative design process embodied in a stochastic evolutionary search. However, combinatorial layout design automation and optimisation using GA is full of challenges. This is because GA is very problem-specific. GA highly depends on a proper chromosome design and genetic operator design specially developed for a specific application problem.
Traditionally, binary representations (e.g. 01001011011 . . . ) are the most common representations for many combinatorial optimisation problems because the binary representation allows a direct and very natural encoding. Chromosomes in GA can also be represented in other forms, such as integer representations, real-valued representations, messy representations and direct representations. Chromosome design is very problem-specific. In some cases, it is not practical to encode a complex design problem using traditional chromosome representation methods. For example, combinatorial layout design involves grouping problems. Designers need to decide how many groups should be divided and which space elements should be grouped together to make a good layout solution. Most previous research using either standard or ordering chromosome design are not suitable for grouping problems because standard or ordering chromosome is object oriented rather than group oriented. Moreover, no previous research can deal with combinatorial layout design problems, which involves solving both grouping problems and space layout design problems at the same time. In fact, using different chromosome design can affect GA performance dramatically. Designing a proper chromosome remains the black art of GA research.
On the other hand, crossover is the most important genetic operator of GA. Crossover aims to combine pieces of genetic information from different individuals in the population. Every generation inherits traits from its parents through genes. In a fixed-length chromosome, the allele (parameter or feature value) for a particular gene (parameter or feature) is coded for at a particular locus (genotype position). It is simple for a standard crossover operator to exchange homologous segments divided by the same crossover point in each parent genotype. However, combinatorial layout design problems cannot be simply encoded into fixed-length chromosomes because numbers of groups and numbers of space elements in each group are variable and unknown beforehand. When variable-length chromosomes are used, no homologous segments divided by the same crossover point in each parent genotype can be exchanged to produce offspring that can inherit meaningful building blocks from both parents. It may produce invalid offspring because genes are combined independently from each of both parents in a cut-and-concentrate manner during a crossover process. A special chromosome requires a specialised crossover operator to inherit and recombine individuals' important genetic properties from generation to generation. Designing a crossover operator to produce valid offspring that can inherit meaningful building blocks from both parents with chromosomes containing grouping genetic information, space layout genetic information and so forth is very challenging.